#!/usr/bin/python3
# -*- coding:utf-8 -*-
# __author__ == taoyulong2018@gmail.com
# __time__ == 2023/7/10 16:16
# ===========================================
#       题目名称： 64. 最小路径和
#       题目地址： https://leetcode.cn/problems/minimum-path-sum/
#       题目描述： https://note.youdao.com/s/LWYgPSzT
# ===========================================


class Solution:
    def minPathSum(self, grid):
        m, n = len(grid), len(grid[0])  # 获取长度
        dp = [[0] * n for _ in range(m)]  # 定义临时数组 用于存放到这里最小的值
        dp[0][0] = grid[0][0]  # 初始化一下
        # x = 0 或 y = 0 求值 即一直往 x 往下走 一直往y 往右走
        for x in range(1, m):
            dp[x][0] = dp[x - 1][0] + grid[x][0]
        for y in range(1, n):
            dp[0][y] = dp[0][y - 1] + grid[0][y]
        for i in range(1, m):
            for j in range(1, n):
                cur_val = grid[i][j]
                top_val, left_val = dp[i - 1][j], dp[i][j - 1]
                # 判断上面加 和 左边加 数最小
                min_val = min(top_val, left_val)
                dp[i][j] = cur_val + min_val
        return dp[m - 1][n - 1]


if __name__ == '__main__':
    s = Solution()
    # 7
    print("grid = [[1,3,1],[1,5,1],[4,2,1]] =>", s.minPathSum(grid=[[1, 3, 1], [1, 5, 1], [4, 2, 1]]))
    # 12
    print("grid = [[1,2,3],[4,5,6]] => ", s.minPathSum(grid=[[1, 2, 3], [4, 5, 6]]))
